#include "tx_memory.h"




#ifndef  UCHAR
#define UCHAR             unsigned char     
#endif

#ifndef VOID
#define VOID               void
#endif

#ifndef CHAR
#define CHAR               char               
#endif

#ifndef INT
#define INT                int                
#endif

#ifndef UINT
#define UINT               unsigned int       
#endif

#ifndef LONG
#define LONG               long               
#endif

#ifndef ULONG
#define ULONG             unsigned long      
#endif

#ifndef SHORT
#define SHORT             short              
#endif

#ifndef USHORT
#define USHORT           unsigned short     
#endif

#ifndef ALIGN_TYPE
#define ALIGN_TYPE      ULONG
#endif

// ------------------------------------------------------------------------------
#define TX_SUCCESS_USER                      ((UINT) 0x00)
#define TX_NULL_USER                         ((VOID *) 0)
#define TX_EMPTY_USER                        ((ULONG)  0)
#define TX_FALSE_USER                        ((UINT)   0)
#define TX_TRUE_USER                         ((UINT)   1)
#define TX_CLEAR_ID_USER                     ((ULONG)  0)
#define TX_NO_SUSPENSIONS_USER               ((UINT)   0)
#define TX_BYTE_POOL_ID_USER                 ((ULONG) 0x42595445)

#define TX_PTR_ERROR_USER                    ((UINT) 0x03)
#define TX_NO_MEMORY_USER                    ((UINT) 0x10)

#define TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(a)             ((UCHAR *) ((VOID *) (a)))
#define TX_UCHAR_POINTER_ADD_USER(a,b)                       (((UCHAR *) (a)) + ((UINT) (b)))
#define TX_UCHAR_POINTER_SUB_USER(a,b)                       (((UCHAR *) (a)) - ((UINT) (b)))
#define TX_BYTE_POOL_TO_UCHAR_POINTER_CONVERT_USER(a)        ((UCHAR *) ((VOID *) (a)))
#define TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(a)   ((UCHAR **) ((VOID *) (a)))
#define TX_UCHAR_POINTER_DIF_USER(a,b)                       ((ULONG)(((UCHAR *) (a)) - ((UCHAR *) (b))))
#define TX_UCHAR_TO_INDIRECT_BYTE_POOL_POINTER_USER(a)       ((TX_BYTE_POOL_OBJ **) ((VOID *) (a)))

#ifndef TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT_USER
#define TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT_USER(a)       ((ALIGN_TYPE *) ((VOID *) (a)))
#endif

#ifndef TX_BYTE_BLOCK_FREE_USER
#define TX_BYTE_BLOCK_FREE_USER                      ((ULONG) 0xFFFFEEEEUL)
#endif

#ifndef TX_BYTE_BLOCK_MIN_USER
#define TX_BYTE_BLOCK_MIN_USER                       ((ULONG) 20)
#endif

#define TX_DISABLE()
#define TX_RESTORE()


/**************************************************************************/
/*                                                                        */
/*    DATE              NAME                      DESCRIPTION             */
/*                                                                        */
/*  05-19-2020     William E. Lamie         Initial Version 6.0           */
/*  09-30-2020     Yuxin Zhou               Modified comment(s),          */
/*                                            resulting in version 6.1    */
/*                                                                        */
/**************************************************************************/
int _tx_byte_pool_create(TX_BYTE_POOL_OBJ *pool_ptr, void *pool_start, uint32_t pool_size)
{
UCHAR               *block_ptr;
UCHAR               **block_indirect_ptr;
UCHAR               *temp_ptr;
ALIGN_TYPE          *free_ptr;

	memset(pool_ptr, 0, (sizeof(TX_BYTE_POOL_OBJ)));
	
    /* Round the pool size down to something that is evenly divisible by 
       an ULONG.  内存池大小 sizeof(ULONG)个字节对齐 */
    pool_size =   (pool_size/(sizeof(ALIGN_TYPE))) * (sizeof(ALIGN_TYPE));

    /* Setup the basic byte pool fields.  */
    // pool_ptr -> tx_byte_pool_name =              name_ptr;

    /* Save the start and size of the pool.  保存内存池起始地址和内存大小 */
    pool_ptr -> tx_byte_pool_start =   TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(pool_start);
    pool_ptr -> tx_byte_pool_size =    pool_size;

    /* Setup memory list to the beginning as well as the search pointer.  设置内存链表首地址，内存池搜索起始地址 */
    pool_ptr -> tx_byte_pool_list =    TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(pool_start);
    pool_ptr -> tx_byte_pool_search =  TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(pool_start);

    /* Initially, the pool will have two blocks.  One large block at the 
       beginning that is available and a small allocated block at the end
       of the pool that is there just for the algorithm.  Be sure to count
       the available block's header in the available bytes count.  */
    // 设置可用内存大小，总的大小减去控制字段
    pool_ptr -> tx_byte_pool_available =   pool_size - ((sizeof(VOID *)) + (sizeof(ALIGN_TYPE)));
    //内存池最开始初始化为两块，一个大的块用于分配内存；一个小的固定块，仅用于内存分配算法计算
    pool_ptr -> tx_byte_pool_fragments =   ((UINT) 2);
    
    /* Each block contains a "next" pointer that points to the next block in the pool followed by a ALIGN_TYPE
       field that contains either the constant TX_BYTE_BLOCK_FREE (if the block is free) or a pointer to the
       owning pool (if the block is allocated).  */
    
    /* Calculate the end of the pool's memory area.   */
    block_ptr =  TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(pool_start);
    block_ptr =  TX_UCHAR_POINTER_ADD_USER(block_ptr, pool_size);  //指向内存池最后地址

    /* Backup the end of the pool pointer and build the pre-allocated block.  
	   内存池最后一块，最后4字节存储TX_BYTE_BLOCK_ALLOC */
    block_ptr =  TX_UCHAR_POINTER_SUB_USER(block_ptr, (sizeof(ALIGN_TYPE)));

    /* Cast the pool pointer into a ULONG.  */
    temp_ptr =             TX_BYTE_POOL_TO_UCHAR_POINTER_CONVERT_USER(pool_ptr);
    block_indirect_ptr =   TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(block_ptr);
    *block_indirect_ptr =  temp_ptr;

    block_ptr =            TX_UCHAR_POINTER_SUB_USER(block_ptr, (sizeof(UCHAR *)));
    block_indirect_ptr =   TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(block_ptr);
    *block_indirect_ptr =  TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(pool_start);

    /* Now setup the large available block in the pool.  */
    temp_ptr =             TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(pool_start);
    block_indirect_ptr =   TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(temp_ptr);
    *block_indirect_ptr =  block_ptr;
    block_ptr =            TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(pool_start);
    block_ptr =            TX_UCHAR_POINTER_ADD_USER(block_ptr, (sizeof(UCHAR *)));
    free_ptr =             TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT_USER(block_ptr);
    *free_ptr =            TX_BYTE_BLOCK_FREE_USER;

    /* Disable interrupts to place the byte pool on the created list.  */
    TX_DISABLE();

    /* Setup the byte pool ID to make it valid.  */
    // pool_ptr -> tx_byte_pool_id =  TX_BYTE_POOL_ID_USER;

    /* Restore interrupts.  */
    TX_RESTORE();

    /* Return TX_SUCCESS.  */
    return(TX_SUCCESS_USER);
}

/*
******************************************************************************************
内存搜索 -----------------------------------------------------------------
******************************************************************************************
*/
static unsigned char  *_tx_byte_pool_search( TX_BYTE_POOL_OBJ *pool_ptr, uint32_t memory_size)
{
UCHAR           *current_ptr;
UCHAR           *next_ptr;
UCHAR           **this_block_link_ptr;
UCHAR           **next_block_link_ptr;
ULONG           available_bytes;
UINT            examine_blocks;
UINT            first_free_block_found =  TX_FALSE_USER;

ALIGN_TYPE      *free_ptr;
UCHAR           *work_ptr;
	
    /* Disable interrupts.  */
    TX_DISABLE();

    /* First, determine if there are enough bytes in the pool.  */
    if (memory_size >= pool_ptr -> tx_byte_pool_available)
    {
        /* Restore interrupts.  */
        TX_RESTORE();
        /* Not enough memory, return a NULL pointer.  */
        current_ptr =  TX_NULL_USER;
    }
    else
    {
        /* Walk through the memory pool in search for a large enough block.  */
        current_ptr =      pool_ptr -> tx_byte_pool_search;
        examine_blocks =   pool_ptr -> tx_byte_pool_fragments + ((UINT) 1);
        available_bytes =  ((ULONG) 0);
        do
        {
            /* Check to see if this block is free.  */
            work_ptr =  TX_UCHAR_POINTER_ADD_USER(current_ptr, (sizeof(UCHAR *)));
            free_ptr =  TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT_USER(work_ptr);
            if ((*free_ptr) == TX_BYTE_BLOCK_FREE_USER)
            {
                /* Determine if this is the first free block.  */
                if (first_free_block_found == TX_FALSE_USER)
                {
                    /* This is the first free block.  */
                    pool_ptr->tx_byte_pool_search =  current_ptr;
                
                    /* Set the flag to indicate we have found the first free
                       block.  */
                    first_free_block_found =  TX_TRUE_USER;
                }

                /* Block is free, see if it is large enough.  */

                /* Pickup the next block's pointer.  */
                this_block_link_ptr =  TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(current_ptr);
                next_ptr =             *this_block_link_ptr;

                /* Calculate the number of bytes available in this block.  */
                available_bytes =   TX_UCHAR_POINTER_DIF_USER(next_ptr, current_ptr);
                available_bytes =   available_bytes - ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)));

                /* If this is large enough, we are done because our first-fit algorithm
                   has been satisfied!  */
                if (available_bytes >= memory_size)
                {
                    /* Get out of the search loop!  */
                    break;
                }
                else
                {
                    /* Clear the available bytes variable.  */
                    available_bytes =  ((ULONG) 0);

                    /* Not enough memory, check to see if the neighbor is 
                       free and can be merged.  */
                    work_ptr =  TX_UCHAR_POINTER_ADD_USER(next_ptr, (sizeof(UCHAR *)));
                    free_ptr =  TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT_USER(work_ptr);
                    if ((*free_ptr) == TX_BYTE_BLOCK_FREE_USER)
                    {
                        /* Yes, neighbor block can be merged!  This is quickly accomplished
                           by updating the current block with the next blocks pointer.  */
                        next_block_link_ptr =  TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(next_ptr);
                        *this_block_link_ptr =  *next_block_link_ptr;

                        /* Reduce the fragment total.  We don't need to increase the bytes
                           available because all free headers are also included in the available
                           count.  */
                        pool_ptr -> tx_byte_pool_fragments--;

                        /* See if the search pointer is affected.  */
                        if (pool_ptr -> tx_byte_pool_search ==  next_ptr)
                        {
                    
                            /* Yes, update the search pointer.   */
                            pool_ptr -> tx_byte_pool_search =  current_ptr;
                        }
                    }
                    else
                    {
                        /* Neighbor is not free so we can skip over it!  */
                        next_block_link_ptr =  TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(next_ptr);
                        current_ptr =  *next_block_link_ptr;

                        /* Decrement the examined block count to account for this one.  */
                        if (examine_blocks != ((UINT) 0))
                        {
                            examine_blocks--;
                        }
                    }
                }
            }
            else
            {
                /* Block is not free, move to next block.  */
                this_block_link_ptr =  TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(current_ptr);
                current_ptr =  *this_block_link_ptr;
            }

            /* Another block has been searched... decrement counter.  */
            if (examine_blocks != ((UINT) 0))
            {
                examine_blocks--;
            }
            /* Restore interrupts temporarily.  */
            TX_RESTORE();

            /* Disable interrupts.  */
            TX_DISABLE();

        } while(examine_blocks != ((UINT) 0));

        /* Determine if a block was found.  If so, determine if it needs to be
           split.  */
        if (available_bytes != ((ULONG) 0))
        {
            /* Determine if we need to split this block.  */
            if ((available_bytes - memory_size) >= ((ULONG) TX_BYTE_BLOCK_MIN_USER))
            {
                /* Split the block.  */
                next_ptr =  TX_UCHAR_POINTER_ADD_USER(current_ptr, (memory_size + ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)))));

                /* Setup the new free block.  */
                next_block_link_ptr =   TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(next_ptr);
                this_block_link_ptr =   TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(current_ptr);
                *next_block_link_ptr =  *this_block_link_ptr;
                work_ptr =              TX_UCHAR_POINTER_ADD_USER(next_ptr, (sizeof(UCHAR *)));
                free_ptr =              TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT_USER(work_ptr);
                *free_ptr =             TX_BYTE_BLOCK_FREE_USER;

                /* Increase the total fragment counter.  */
                pool_ptr -> tx_byte_pool_fragments++;

                /* Update the current pointer to point at the newly created block.  */
                *this_block_link_ptr =  next_ptr;
    
                /* Set available equal to memory size for subsequent calculation.  */
                available_bytes =  memory_size;
            }

            /* In any case, mark the current block as allocated.  */
            work_ptr =              TX_UCHAR_POINTER_ADD_USER(current_ptr, (sizeof(UCHAR *)));
            this_block_link_ptr =   TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(work_ptr);
            *this_block_link_ptr =  TX_BYTE_POOL_TO_UCHAR_POINTER_CONVERT_USER(pool_ptr);

            /* Reduce the number of available bytes in the pool.  */
            pool_ptr -> tx_byte_pool_available =  (pool_ptr -> tx_byte_pool_available - available_bytes) - ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)));

            /* Determine if the search pointer needs to be updated. This is only done
               if the search pointer matches the block to be returned.  */
            if (current_ptr == pool_ptr -> tx_byte_pool_search)
            {

                /* Yes, update the search pointer to the next block.  */
                this_block_link_ptr =   TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(current_ptr);
                pool_ptr -> tx_byte_pool_search =  *this_block_link_ptr;
            }
            /* Restore interrupts.  */
            TX_RESTORE();

            /* Adjust the pointer for the application.  */
            current_ptr =  TX_UCHAR_POINTER_ADD_USER(current_ptr, (((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE)))));
        }
        else
        {
            /* Restore interrupts.  */
            TX_RESTORE();

            /* Set current pointer to NULL to indicate nothing was found.  */
            current_ptr =  TX_NULL_USER;
        }
    }
    /* Return the search pointer.  */
    return(current_ptr);
}


/**************************************************************************/
/*                                                                        */
/*  RELEASE HISTORY                                                       */
/*                                                                        */
/*    DATE              NAME                      DESCRIPTION             */
/*                                                                        */
/*  05-19-2020     William E. Lamie         Initial Version 6.0           */
/*  09-30-2020     Yuxin Zhou               Modified comment(s),          */
/*                                            resulting in version 6.1    */
/*                                                                        */
/**************************************************************************/
int _tx_byte_allocate( TX_BYTE_POOL_OBJ *pool_ptr, void **memory_ptr, uint32_t memory_size)
{
UINT                        status;
UCHAR                       *work_ptr;
// UINT                        suspended_count;
UINT                        finished;

    /* Round the memory size up to the next size that is evenly divisible by
       an ALIGN_TYPE (this is typically a 32-bit ULONG).  This guarantees proper alignment.  
       字节对齐 */
    memory_size = (((memory_size + (sizeof(ALIGN_TYPE)))-((ALIGN_TYPE) 1))/(sizeof(ALIGN_TYPE))) * (sizeof(ALIGN_TYPE));

    /* Disable interrupts.  */
    TX_DISABLE();

    /* Set the search finished flag to false.  */
    finished =  TX_FALSE_USER;

    /* Loop to handle cases where the owner of the pool changed.  */
    do
    {
        /* Restore interrupts.  */
        TX_RESTORE();

        /* At this point, the executing thread owns the pool and can perform a search
           for free memory.  */
        work_ptr =  _tx_byte_pool_search(pool_ptr, memory_size);

        /* Lockout interrupts.  */
        TX_DISABLE();

        /* Determine if we are finished.  */
        if (work_ptr != TX_NULL_USER)
        {
            /* Yes, we have found a block the search is finished.  */
            finished =  TX_TRUE_USER;
        }
    } while (finished == TX_FALSE_USER);

    /* Copy the pointer into the return destination.  */
    *memory_ptr =  (VOID *) work_ptr;

    /* Determine if memory was found.  */
    if (work_ptr != TX_NULL_USER)
    {
        /* Restore interrupts.  */
        TX_RESTORE();
        
        /* Set the status to success.  */
        status =  TX_SUCCESS_USER;
    }
    else
    {
        /* Restore interrupts.  */
        TX_RESTORE();

        /* Immediate return, return error completion.  */
        status =  TX_NO_MEMORY_USER;
    }

    /* Return completion status.  */
    return(status);
}

/**************************************************************************/
// https://blog.csdn.net/qq_45683435/article/details/104259293?utm_medium=distribute.pc_relevant.none-task-blog-title-3&spm=1001.2101.3001.4242
/*  RELEASE HISTORY                                                       */
/*                                                                        */
/*    DATE              NAME                      DESCRIPTION             */
/*                                                                        */
/*  05-19-2020     William E. Lamie         Initial Version 6.0           */
/*  09-30-2020     Yuxin Zhou               Modified comment(s),          */
/*                                            resulting in version 6.1    */
/*                                                                        */
/**************************************************************************/
int _tx_byte_release(TX_BYTE_POOL_OBJ *_pool_ptr, void *memory_ptr)
{
UINT                status;
TX_BYTE_POOL_OBJ    *pool_ptr;
UCHAR               *work_ptr;
UCHAR               *temp_ptr;
UCHAR               *next_block_ptr;
// UINT                suspended_count;
// ULONG               memory_size;
ALIGN_TYPE          *free_ptr;
TX_BYTE_POOL_OBJ   **byte_pool_ptr;
UCHAR               **block_link_ptr;
// UCHAR               **suspend_info_ptr;

    /* Default to successful status.  */
    status =  TX_SUCCESS_USER;
    
    /* Set the pool pointer to NULL.  */
    pool_ptr =  TX_NULL_USER;

    /* Lockout interrupts.  */
    TX_DISABLE();

    /* Determine if the memory pointer is valid.  记录要释放内存起始地址 */
    work_ptr =  TX_VOID_TO_UCHAR_POINTER_CONVERT_USER(memory_ptr);
    if (work_ptr != TX_NULL_USER)
    {
        /* Back off the memory pointer to pickup its header.  */
        /* 后退sizeof(CHAR_PTR) +sizeof(ULONG)字节是所在块内存控制字段首地址 */
        work_ptr =  TX_UCHAR_POINTER_SUB_USER(work_ptr, ((sizeof(UCHAR *)) + (sizeof(ALIGN_TYPE))));

        /* There is a pointer, pickup the pool pointer address.  */
        /* 检查控制字段，第4到8字节，不等于TX_BYTE_BLOCK_FREE，说明不是空闲内存 */
        temp_ptr =  TX_UCHAR_POINTER_ADD_USER(work_ptr, (sizeof(UCHAR *)));
        free_ptr =  TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT_USER(temp_ptr);
        if ((*free_ptr) != TX_BYTE_BLOCK_FREE_USER)
        {
            /* Pickup the pool pointer.  第4到8字节存储了内存池管理结构指针 */
            temp_ptr =  TX_UCHAR_POINTER_ADD_USER(work_ptr, (sizeof(UCHAR *)));
            byte_pool_ptr =  TX_UCHAR_TO_INDIRECT_BYTE_POOL_POINTER_USER(temp_ptr);   // 转换为对应的控制块地址 

            pool_ptr =  *byte_pool_ptr;

            /* See if we have a valid pool pointer.  
               检查内存池管理结构指针，内存池是否有效 */
            if (pool_ptr == TX_NULL_USER)
            {
                /* Return pointer error.  */
                status =  TX_PTR_ERROR_USER;
            }
            else
            {
                /* See if we have a valid pool.  */
                // if (pool_ptr->tx_byte_pool_id != TX_BYTE_POOL_ID_USER)
                // {
                //     /* Return pointer error.  */
                //     status = TX_PTR_ERROR_USER;

                //     /* Reset the pool pointer is NULL.  */
                //     pool_ptr = TX_NULL_USER;
                // }
            }
        }
        else
        {
            /* Return pointer error.  */
            status =  TX_PTR_ERROR_USER;
        }
    }
    else
    {
        /* Return pointer error.  */
        status =  TX_PTR_ERROR_USER;
    }

    /* Determine if the pointer is valid.  */
    if (pool_ptr == TX_NULL_USER)
    {
        /* Restore interrupts.  */
        TX_RESTORE();
    }
    else
    {
        /* Release the memory.  释放内存，标记为TX_BYTE_BLOCK_FREE，成为空闲块 */
        temp_ptr =   TX_UCHAR_POINTER_ADD_USER(work_ptr, (sizeof(UCHAR *)));
        free_ptr =   TX_UCHAR_TO_ALIGN_TYPE_POINTER_CONVERT_USER(temp_ptr);
        *free_ptr =  TX_BYTE_BLOCK_FREE_USER;

        /* Update the number of available bytes in the pool.  
           增加可用内存*((CHAR_PTR *)(work_ptr))为相邻的下一块内存地址，(*((CHAR_PTR *)(work_ptr)) - work_ptr)就是本块内存的大小了 */
        block_link_ptr =  TX_UCHAR_TO_INDIRECT_UCHAR_POINTER_CONVERT_USER(work_ptr);
        next_block_ptr =  *block_link_ptr;
        pool_ptr -> tx_byte_pool_available =  
        pool_ptr -> tx_byte_pool_available + TX_UCHAR_POINTER_DIF_USER(next_block_ptr, work_ptr);

        /* Determine if the free block is prior to current search pointer.  */
        if (work_ptr < (pool_ptr -> tx_byte_pool_search))
        {
            /* Yes, update the search pointer to the released block.  */
            /* 本块内存已经释放，那么搜索的起始地址更新为本快内存起始地址，下一次搜索从这一块空闲内存开始 */
            pool_ptr -> tx_byte_pool_search =  work_ptr;
        }

        /* No, threads suspended, restore interrupts.  */
        TX_RESTORE();
    }
    /* Return completion status.  */
    return(status);
}




